package it.storm.solution;

/**
 * 605. 种花问题
 * https://leetcode-cn.com/problems/can-place-flowers/
 */
public class Solutions_605 {
    public static void main(String[] args) {
//        int[] flowerbed = {1, 0, 0, 0, 1};
//        int n = 1;  // output: true

        int[] flowerbed = {1, 0, 0, 0, 1, 0, 0};
        int n = 2;  // output: true

//        int[] flowerbed = {1, 0, 0, 0, 1};
//        int n = 2;  // output: false

        boolean result = canPlaceFlowers(flowerbed, n);
        System.out.println(result);
    }

    public static boolean canPlaceFlowers(int[] flowerbed, int n) {
        // 开头默认设置一个 0
        // [0, 0, 1] 的情况，是可以种 1 朵花的
        int cnt = 1;

        for (int i = 0; i < flowerbed.length; i++) {
            if (flowerbed[i] == 0) {
                cnt ++;
            } else {
                // 连续 3 个 0，可以种一朵
                // 连续 4 个 0，可以种一朵
                // 连续 5 个 0，可以种两朵
                n -= (cnt - 1) / 2;
                cnt = 0;
            }
            if (n == 0) {
                return true;
            }
        }
        // 末尾默认设置一个 0
        // [1, 0, 0] 的情况，是可以种 1 朵花的
        if (cnt > 0) {
            n -= cnt / 2;
        }
        return n <= 0;
    }
}
